home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 501-525 / disk_519 / avlsort / avltree.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  15KB  |  528 lines
  1. /*    avl.c        AVL routines
  2.  
  3.     Copyright 1988 Zinn Computer Company
  4.             by Mark E. Mallett
  5.  
  6.     All rights reserved;
  7.     This software may be used at will, provided that all credits
  8. and style be left in place, and that its distribution is not restricted.
  9. Bug fixes and improvements are welcomed, please send these back to
  10. me at mem@zinn.MV.COM
  11.  
  12.     This is a general-purpose implementation of AVL trees in C.
  13. It is derived from the description of AVL (Adelson-Velskii and Landis)
  14. trees found in Knuth's "The Art of Computer Programming Volume 3:
  15. Searching and Sorting" (Addison-Wesley, 1973) pgs 451-471.
  16.  
  17.     The routines in this file deal with tree maintenance only.
  18. These routines are only concerned with the arrangement of the nodes
  19. in the tree.  Composition of those nodes is left to outside knowledge.
  20. The caller must construct an AVL tree header structure which specifies
  21. routines that deal with nodes (comparison, construction, and deletion).
  22. Please see the attached document for further information.
  23.  
  24. Contained in this file:
  25.  
  26.     avlfind        Find a node in an AVL tree
  27.     avldelete    Delete a node from an AVL tree
  28.     avlinsert    Insert a node into an AVL tree
  29.  
  30.     +-----------------------------------------------+
  31.     | rlp910619 -- I've modified this to include    |
  32.     | prototypes and register arguments.        |
  33.     +-----------------------------------------------+
  34. */
  35.  
  36. #include <stdio.h>
  37.  
  38. #include "avltree.h"
  39.  
  40.     /*--------------------------------------------------------------
  41.      * rlp900624 -- Support for Lattice-style prototypes
  42.      *    If MSDOS, I assume Microsoft C compiler for DOS and OS/2
  43.      *    If Lattice, I assume Lattice C compiler for Amiga
  44.      *--------------------------------------------------------------
  45.      */
  46.  
  47. #ifndef __ARGS
  48.  #if    defined(MSDOS) || defined(LATTICE)
  49.   #define __ARGS(a) a
  50.  #else
  51.   #define __ARGS(a) ()
  52.  #endif
  53. #endif
  54.  
  55.  
  56. /* Local definitions */
  57.  
  58.  
  59. /* External routines */
  60.  
  61.  
  62. /* External data */
  63.  
  64.  
  65. /* Local routines */
  66.  
  67.     /*--------------------------------------------------------
  68.      * rlp900624 -- Added Lattice-style prototypes.  See AVL.H
  69.      *--------------------------------------------------------
  70.      */
  71.  
  72. AVLNODE *  __regargs avlfind (AVLTREE * treeP, void *keyP);
  73. int       __regargs avlinsert (AVLTREE * treeP, void *keyP, void *dataP);
  74. int       __regargs avldelete (AVLTREE * treeP, void *keyP);
  75. static int __regargs delete (AVLTREE * treeP, AVLNODE ** topPP, void *keyP);
  76. static int __regargs balance (AVLNODE ** branchPP);
  77.  
  78. /* Local data */
  79.  
  80. /*
  81.  
  82. *//* avlfind( treeP, keyP )
  83.  
  84.     Lookup a value in an avl tree
  85.  
  86. Accepts :
  87.  
  88.     treeP        Address of the AVLTREE structure describing the tree.
  89.     keyP        Address of a key for the node.  Interpretation of
  90.               the key is left to the "compare key" routine.
  91.  
  92. Returns :
  93.  
  94.     <value>        The address of the node if it is found,
  95.             NULL if it is not.
  96.  
  97.  
  98. */
  99.  
  100. AVLNODE * __regargs
  101. avlfind( treeP, keyP )
  102.     AVLTREE        *treeP;        /* Address of the tree struct */
  103.     void        *keyP;        /* Address of the key info */
  104.  
  105. {
  106.     AVLNODE        *nodeP;        /* To follow the tree with */
  107.  
  108.     /* Traverse the tree until the node is found or the tree runs out. */
  109.     for( nodeP = treeP->t_rootP; nodeP != NULL; ) {
  110.     switch( (*treeP->t_cmprtc)( keyP, nodeP ) ) {
  111.         case 0:            /* Node found! */
  112.         return( nodeP );    /* Go ahead and return it */
  113.         
  114.         case -1:            /* Take left branch */
  115.         nodeP = nodeP->n_leftP;
  116.         break;
  117.  
  118.         case 1:            /* Take right branch */
  119.             nodeP = nodeP->n_rightP;
  120.         break;
  121.     }
  122.     }
  123.  
  124.     /* Didn't find the node in the tree. */
  125.     return( NULL );
  126. }
  127. /*
  128.  
  129. *//* avlinsert( treeP, keyP, dataP )
  130.  
  131.     Insert a node in an avl tree
  132.  
  133. Accepts :
  134.  
  135.     treeP        The address of the tree header structure.
  136.     keyP        The address of the key for the node.  Interpretation
  137.               of the key is by the compare and node-create
  138.               routines specified in the avl tree header.
  139.     dataP        The address of the data info for the tree.  The
  140.              interpretation of this is left to the create-node
  141.              routine specified in the avl tree header.
  142.  
  143. Returns :
  144.  
  145.     <value>        -1 if failure of some kind
  146.              0 if successful insertion
  147.              1 if duplicate key
  148.  
  149. Notes:
  150.  
  151.     The tree header structure specifies a node construction routine
  152.     that is responsible for allocating a node and putting the new
  153.     key and data information into it.  It is called as follows:
  154.  
  155.        nodeP = construct( treeP, keyP, dataP, enodeP )
  156.  
  157.     treeP, keyP, and dataP are as passed to this routine.  "enodeP"
  158.     is NULL if a new node is required; otherwise it is the address
  159.     of an already existing node that matches the specified key -
  160.     in this case it is up to the constructor to decide whether to
  161.     overwrite the existing node or to call it an error.  The routine
  162.     is expected to return the address of the AVLNODE structure
  163.     that is allocated (if enode==NULL ) or that exists, or to
  164.     return NULL if the node is not made (or used).
  165.  
  166. */
  167.  
  168. int __regargs
  169. avlinsert( treeP, keyP, dataP )
  170.     AVLTREE        *treeP;        /* Addr of the tree struct */
  171.     void        *keyP;        /* The key for insertion insert */
  172.     void        *dataP;        /* The data for the insertion */
  173. {
  174.     int        direction;    /* Direction we took from decision pt */
  175.     AVLNODE        *nodeP;        /* Node that we're looking at */
  176.     AVLNODE        *clearP;    /* For erasing tracks */
  177.     AVLNODE        **nodePP;    /* Pointer to the next link */
  178.     AVLNODE        **topPP;    /* Pointer to the top pointer */
  179.  
  180.     /* Traverse the tree to find an insertion point (or existing key).
  181.        Along the way, we'll adjust the balance counts on the nodes as
  182.        we pass by them.  And as we do this, we'll remember the potential
  183.        tree rotation point (the lowest non-balanced treetop) as well as
  184.        the direction we took from it (in case we have to fix it up when
  185.        we discover a lower balance point). */
  186.  
  187.     nodePP = topPP = &(treeP->t_rootP);    /* Start at top of tree */
  188.     direction = 0;            /* Haven't gone anywhwere yet */
  189.     while( (nodeP = *nodePP) != NULL ) { /* Till we reach the end */
  190.  
  191.     /* See if we're at a potential balance point */
  192.     if ( nodeP->n_balance != 0 ) {
  193.  
  194.         /* New balance point.  Erase any trail we've made to here */
  195.         if ( direction != 0 )
  196.         for( clearP = *topPP; clearP != nodeP;
  197.                  direction = clearP->n_balance ) {
  198.             clearP->n_balance -= direction;
  199.             if ( direction < 0 )
  200.             clearP = clearP->n_leftP;
  201.             else
  202.             clearP = clearP->n_rightP;
  203.         }
  204.          direction = 0;        /* So we make new balance point */
  205.          topPP = nodePP;        /* Remember new top */
  206.     }
  207.  
  208.     /* Now follow the tree... */
  209.     switch( (*treeP->t_cmprtc)( keyP, nodeP ) ) {
  210.         case 0:            /* Match */
  211.         /* Here we have a duplicate node.  First erase the
  212.            trail that we left. */
  213.         if ( direction != 0 )
  214.             for( clearP = *topPP; clearP != NULL;
  215.                 direction = clearP->n_balance ) {
  216.             clearP->n_balance -= direction;
  217.             if ( direction < 0 )
  218.                 clearP = clearP->n_leftP;
  219.             else
  220.                 clearP = clearP->n_rightP;
  221.             }
  222.  
  223.         /* Give the node to the node constructor and
  224.            see what we get. */
  225.         if ( (*treeP->t_mknode)( treeP, keyP, dataP, nodeP ) == NULL )
  226.             return( 1 );    /* Duplicate key */
  227.         return( 0 );        /* Return success */
  228.  
  229.         case -1:            /* Go left */
  230.         nodePP = &(nodeP->n_leftP);
  231.         --nodeP->n_balance;
  232.         if ( direction == 0 )    /* Remember balance point branch? */
  233.             direction = -1;
  234.         break;
  235.  
  236.         case 1:            /* Go right */
  237.         nodePP = &(nodeP->n_rightP);
  238.         ++nodeP->n_balance;
  239.         if ( direction == 0 )
  240.             direction = 1;
  241.         break;
  242.     }
  243.     }
  244.  
  245.     /* Here we've gotten to the bottom, so make a new node */
  246.     nodeP = (*treeP->t_mknode)( treeP, keyP, dataP, (AVLNODE *)NULL );
  247.     if ( nodeP != NULL ) {        /* Successful node creation? */
  248.     nodeP->n_balance = 0;        /* Fill in the nitty gritty */
  249.     nodeP->n_leftP = nodeP->n_rightP = NULL;
  250.     *nodePP = nodeP;        /* Link it in */
  251.     balance( topPP );        /* May need reshaping now */
  252.     return( 0 );            /* Return success */
  253.     }
  254.  
  255.     /* Error making node.  Erase our trail */
  256.     if ( direction != 0 )
  257.     for( clearP = *topPP; clearP != NULL;
  258.             direction = clearP->n_balance ) {
  259.         clearP->n_balance -= direction;
  260.         if ( direction < 0 )
  261.         clearP = clearP->n_leftP;
  262.         else
  263.         clearP = clearP->n_rightP;
  264.     }
  265.     return( -1 );            /* Return error */
  266. }
  267. /*
  268.  
  269. *//* avldelete( treeP, keyP )
  270.  
  271.     Delete a node from an AVL tree
  272.  
  273. Accepts:
  274.  
  275.     treeP        Address of the tree definition structure.
  276.     keyP        Address of the key for the node.  Interpretation
  277.              of the key is left to the key-compare routine
  278.              specified in the tree header.
  279.  
  280. Returns :
  281.  
  282.      <value>        0 if deleted OK
  283.             -1 if not found
  284.  
  285. */
  286.  
  287. int __regargs
  288. avldelete( treeP, keyP )
  289.     AVLTREE        *treeP;        /* Addr of tree block */
  290.     void        *keyP;        /* Addr of key */
  291. {
  292.     /* Simply call a local deletion routine */
  293.     if ( delete( treeP, &treeP->t_rootP, keyP ) < 0 )
  294.     return( -1 );            /* error in delete */
  295.     return( 0 );            /* Fine and dandy */
  296. }
  297. /*
  298.  
  299. *//* delete( treeP, topPP, keyP )
  300.  
  301.     Local routine to delete from a subtree
  302.  
  303. Accepts:
  304.  
  305.     treeP        Address of the tree definition structure
  306.     topPP        Address of the pointer to this branch
  307.     keyP        Address of the key for the node.  Interpretation
  308.              of the key is left to the key-compare routine
  309.              specified in the tree header.
  310.  
  311. Returns :
  312.  
  313.      <value>        -1 if not found;
  314.              0 if deleted and tree did not shrink;
  315.              1 if deleted and tree shrunk by 1.
  316.  
  317. */
  318.  
  319. static int __regargs
  320. delete( treeP, topPP, keyP )
  321.     AVLTREE        *treeP;        /* Addr of tree block */
  322.     AVLNODE        **topPP;    /* Addr of ptr to branch */
  323.     void        *keyP;        /* Addr of key */
  324. {
  325.     int        i;        /* Scratch */
  326.     int        sts;
  327.     int        cmp;        /* Comparison result */
  328.     AVLNODE        *nodeP;        /* Node pointer */
  329.     AVLNODE        *node1P;    /* Another one */
  330.     AVLNODE        *tempP;        /* For exchanging */
  331.     AVLNODE        **linkPP;    /* Addr of a node pointer */
  332.  
  333.     nodeP = *topPP;            /* Get addr of node */
  334.     if ( nodeP == NULL )        /* If we hit bottom */
  335.     return( -1 );            /*  then we didn't find it */
  336.  
  337.     cmp = (*treeP->t_cmprtc)( keyP, nodeP );
  338.     if ( cmp == 0 ) {
  339.     /* We've found the node to delete.  If it has no children we
  340.        can just get rid of it.  Otherwise we have to remove it
  341.        from the tree somehow.  If one or the other subtrees
  342.         is empty, then it is easy. */
  343.  
  344.     if ( nodeP->n_leftP == NULL ) {
  345.         /* Just shorten the right branch (even if it doesn't exist) */
  346.         *topPP = nodeP->n_rightP;
  347.         (*treeP->t_rmnode)( treeP, nodeP );
  348.         return( 1 );        /* Branch shrunk */
  349.     }
  350.  
  351.     if ( nodeP->n_rightP == NULL ) {
  352.         /* Shorten the left branch */
  353.         *topPP = nodeP->n_leftP;
  354.         (*treeP->t_rmnode)( treeP, nodeP );
  355.         return( 1 );
  356.     }
  357.  
  358.     /* Both subtrees exist.  Exchange this node with the one
  359.        logically adjacent (in value) to it.  Then this node
  360.        will be at the end of a branch and we can recurse to
  361.        delete it. */
  362.  
  363.     if( nodeP->n_balance < 0 ) {
  364.         node1P = nodeP->n_leftP;
  365.         linkPP = &(node1P->n_leftP);
  366.         for( ; node1P->n_rightP != NULL; node1P = node1P->n_rightP )
  367.         linkPP = &(node1P->n_rightP);
  368.         cmp = -1;            /* We went left */
  369.     } else {
  370.         node1P = nodeP->n_rightP;
  371.         linkPP = &(node1P->n_rightP);
  372.         for( ; node1P->n_leftP != NULL; node1P = node1P->n_leftP )
  373.         linkPP = &(node1P->n_leftP);
  374.         cmp = 1;            /* We're going right */
  375.     }
  376.  
  377.     /* Exchange the two nodes.  We have to actually exchange by
  378.        relinking rather than copying since the node may imply
  379.        other stuff that we don't know about here. */
  380.  
  381.     tempP = node1P->n_rightP;    /* Exchange right pointers */
  382.     node1P->n_rightP = nodeP->n_rightP;
  383.     nodeP->n_rightP = tempP;
  384.  
  385.     tempP = node1P->n_leftP;    /* Exchange left pointers */
  386.     node1P->n_leftP = nodeP->n_leftP;
  387.     nodeP->n_leftP = tempP;
  388.  
  389.     i = node1P->n_balance;        /* Exchange balance values */
  390.     node1P->n_balance = nodeP->n_balance;
  391.     nodeP->n_balance = i;
  392.  
  393.     *topPP = node1P;        /* Exchange the nodes */
  394.     *linkPP = nodeP;
  395.     nodeP = node1P;            /* Pretend we're here */
  396.     }
  397.  
  398.     /* Remove the node from left or right subtree depending on "cmp" */
  399.     switch ( cmp ) {
  400.     case -1:
  401.         sts = delete( treeP, &nodeP->n_leftP, keyP );
  402.         if ( sts == 1 )        /* If it shrunk */
  403.         ++nodeP->n_balance;    /*  reflect that in the balance */
  404.         break;
  405.  
  406.     case 1:
  407.         sts = delete( treeP, &nodeP->n_rightP, keyP );
  408.         if ( sts == 1 )        /* Right branch shrunk? */
  409.         --nodeP->n_balance;    /*  adjust the balance */
  410.         break;
  411.     }
  412.  
  413.     if ( sts == 1 )            /* If we changed balance */
  414.     if ( nodeP->n_balance != 0 )    /*  if it's 0 it shrunk but is ok */
  415.         sts = balance( topPP );    /*    otherwise fix it up */
  416.     return( sts );
  417. }
  418. /*
  419.  
  420. *//* balance( branchPP )
  421.  
  422.     Local routine to balance a branch
  423.  
  424. Accepts :
  425.  
  426.     branchPP    Addr of the variable pointing to the top n
  427.  
  428. Returns :
  429.  
  430.     <value>        0 if branch has stayed the same height;
  431.             1 if branch shrunk by one.
  432.  
  433.  
  434. Notes :
  435.  
  436.     This routine accepts a branch in conditions left by the
  437. internal routines only.  No other cases are dealt with.
  438.  
  439. */
  440.  
  441. static int __regargs
  442. balance( branchPP )
  443.     AVLNODE        **branchPP;    /* Ptr to top node */
  444. {
  445.     int        shrunk;        /* Whether we shrunk */
  446.     AVLNODE        *nodeP;        /* Current top node */
  447.     AVLNODE        *leftP;        /* Left child */
  448.     AVLNODE        *rightP;    /* Right child */
  449.     AVLNODE        *migP;        /* A ndoe that migrates */
  450.  
  451.     /* Pick up relevant information */
  452.     nodeP = *branchPP;
  453.     leftP = nodeP->n_leftP;
  454.     rightP = nodeP->n_rightP;
  455.     shrunk = 0;                /* Assume tree doesn't shrink */
  456.  
  457.     /* Process according to out-of-balance amount, if any */
  458.     switch( nodeP->n_balance ) {
  459.     case -2:            /* Too heavy on left */
  460.         if ( leftP->n_balance <= 0 ) {
  461.  
  462.         /* Single rotation */
  463.         *branchPP = leftP;
  464.         nodeP->n_leftP = leftP->n_rightP;
  465.         leftP->n_rightP = nodeP;
  466.         ++leftP->n_balance;
  467.         nodeP->n_balance = -(leftP->n_balance);
  468.         if ( leftP->n_balance == 0 )
  469.             shrunk = 1;
  470.         }
  471.         else {            /* Migration of inner node to top */
  472.         migP = leftP->n_rightP;
  473.         leftP->n_rightP = migP->n_leftP;
  474.         nodeP->n_leftP = migP->n_rightP;
  475.         migP->n_leftP = leftP;
  476.         migP->n_rightP = nodeP;
  477.         *branchPP = migP;
  478.         if ( migP->n_balance < 0 ) {
  479.             leftP->n_balance = 0;
  480.             nodeP->n_balance = 1;
  481.         }
  482.         else if ( migP->n_balance > 0 ) {
  483.             leftP->n_balance = -1;
  484.             nodeP->n_balance = 0;
  485.         }
  486.         else
  487.             leftP->n_balance = nodeP->n_balance = 0;
  488.         migP->n_balance = 0;
  489.         shrunk = 1;
  490.         }
  491.         break;
  492.             
  493.     case  2:            /* Too heavy on right */
  494.         if ( rightP->n_balance >= 0 ) {
  495.  
  496.         /* Single rotation */
  497.         *branchPP = rightP;
  498.         nodeP->n_rightP = rightP->n_leftP;
  499.         rightP->n_leftP = nodeP;
  500.         --rightP->n_balance;
  501.         nodeP->n_balance = -(rightP->n_balance);
  502.         if ( rightP->n_balance == 0 )
  503.             shrunk = 1;
  504.         }
  505.         else {            /* Migration of inner node */
  506.         migP = rightP->n_leftP;
  507.         rightP->n_leftP = migP->n_rightP;
  508.         nodeP->n_rightP = migP->n_leftP;
  509.         migP->n_leftP = nodeP;
  510.         migP->n_rightP = rightP;
  511.         *branchPP = migP;
  512.         if ( migP->n_balance < 0 ) {
  513.             nodeP->n_balance = 0;
  514.             rightP->n_balance = 1;
  515.         }
  516.         else if ( migP->n_balance > 0 ) {
  517.             nodeP->n_balance = -1;
  518.             rightP->n_balance = 0;
  519.         }
  520.         else
  521.             nodeP->n_balance = rightP->n_balance = 0;
  522.         migP->n_balance = 0;
  523.         shrunk = 1;
  524.         }
  525.     }
  526.     return( shrunk );
  527. }
  528.